public class test4 {
    //力扣 174.地下城游戏
    public int calculateMinimumHP(int[][] dungeon) {
        //创建dp数组
        //初始化
        //填表
        //返回值
        int m = dungeon.length,n = dungeon[0].length;
        int[][] dp = new int[m+1][n+1];
        //dp表最下面那行
        for(int j = 0;j<n+1;j++){
            dp[m][j] = Integer.MAX_VALUE;
        }
        //dp表最右边那列
        for(int i = 0;i<m+1;i++){
            dp[i][n] = Integer.MAX_VALUE;
        }
        //这里的初始化一定要小心注意，公主的右边和下面应该是1，因为他要活着出去
        dp[m][n-1] = dp[m-1][n] = 1;
        //以某位置为起点，到达下一步需要多少体力点
        for(int i = m-1;i>=0;i--){
            for(int j = n-1;j>=0;j--){
                dp[i][j] = -dungeon[i][j]+Math.min(dp[i][j+1],dp[i+1][j]);
                dp[i][j] = Math.max(dp[i][j],1);
            }
        }

        return dp[0][0];
    }
}
